<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2540：[Ctsc2000]快乐的蜜月</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Ctsc2000]快乐的蜜月</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Ctsc2000]快乐的蜜月</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Ctsc2000]快乐的蜜月                </h1>
                <p>时间限制：3s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p class="MsoNormal" style="margin: 0cm 0cm 0pt"><b style="mso-bidi-font-weight: normal"><span lang="EN-US" style="font-family: 宋体"><o:p><span style="font-size: medium">&nbsp;</span></o:p></span></b></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">位于某个旅游胜地的一家宾馆里，有一个房间是总统套房。由于总统套房价格昂贵，因此常常无人光临。宾馆的经理为了创收，决定将总统套房改建为专门为新婚夫妇服务的蜜月房。宾馆经理不仅大幅度降低了蜜月房的价位，而且还对不同身份的顾客制定了不同的价位，以吸引不同身份、不同消费水平的游客。比如对于来订蜜月房的国内来宾、海外旅客、港澳台同胞</span></span><span style="font-size: medium"><span class="MsoCommentReference"><span lang="EN-US" style="font-family: 宋体; mso-bidi-font-size: 10.5pt"><span style="display: none; mso-hide: all"><span style="mso-special-character: comment">&nbsp;</span></span></span></span><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">等，区别收取费用。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">宾馆经理的举措获得了不同凡响的效果。由于蜜月房环境幽雅，服务周到，因此生意红火。宾馆经理在每年年底都会收到第二年的所有蜜月房预订单。每张预订单包括以下几个必要的信息：到达日期、离去日期和顾客身份。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">由于宾馆只有一间蜜月房，只能同时接待一对新婚夫妇。因此并不是所有的预订要求都能得到满足。当一些预订要求在时间上发生了重叠的时候，我们就称这些预订要求发生了冲突。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">对于那些不与任何其他预订要求发生冲突的预订单，必然会被接受，因为这对宾馆和顾客双方面来说都是件好事。而对于发生冲突的预订要求，宾馆经理则必须拒绝其中的一部分，以保证宾馆有秩序地运转。显然，对于同一时间内发生冲突的预定要求，宾馆经理最多只能接受其中的一个。经理也有可能拒绝同一时间段内的所有预定要求，因为这样可以避免顾客间发生争执。经理在做出决策后，需要将整个计划公布于众，以示公平。这是一个必须慎重的决定，因为它牵涉到诸多方面的因素。经理首先考虑的当然是利润问题。他必然希望获得尽可能多的收入。可是宾馆在获得经济效益的同时，同时也应该兼顾到社会效益</span></span><span style="font-size: medium"><span class="MsoCommentReference"><span lang="EN-US" style="font-family: 宋体; mso-bidi-font-size: 10.5pt"><span style="display: none; mso-hide: all"><span style="mso-special-character: comment">&nbsp;</span></span></span></span><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">，不能太惟利是图，还必须照顾到顾客们的感情。如果宾馆经理单从最大获利角度出发来决定接受或拒绝顾客的预订要求的话，就会引起人们的不满。经理有一个学过市场营销学的顾问。顾问告诉经理，可以采取一种折中的做法，放弃牟利最大的方案，而采纳获利第<span lang="EN-US">k</span>大的方案。他还通过精确的市场分析，找到了<span lang="EN-US">k</span>的最佳取值点，告诉了宾馆经理。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">现在请你帮助宾馆经理，从一大堆预订要求中，在上述原则下寻找到获利第<span lang="EN-US">k</span>大的方案。宾馆经理将根据此方案来决定接受和拒绝哪些预订要求。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: medium"><span lang="EN-US" style="font-family: 宋体; mso-bidi-font-size: 10.0pt"><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span></span><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">当然，可能有若干种方案的获利是一样大的。这时候，它们同属于获利第<span lang="EN-US">i</span>大的方案而不区分看待。例如，假如有<span lang="EN-US">3</span>种方案的收入同时为<span lang="EN-US">3</span>，有<span lang="EN-US">2</span>种方案的收入为<span lang="EN-US">2</span>，则收入为<span lang="EN-US">3</span>的方案都属于获利最大，收入为<span lang="EN-US">2</span>的方案都属于获利第二大。依次类推。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: medium"><span lang="EN-US" style="font-family: 宋体; mso-bidi-font-size: 10.0pt"><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span></span><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">假设所有的住、离店登记都在中午<span lang="EN-US">12</span>点进行。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: medium"><span lang="EN-US" style="font-family: 宋体; mso-bidi-font-size: 10.0pt"><o:p>&nbsp;</o:p></span></span><span lang="EN-US" style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"></p></p><hr/><h3>输入格式</h3><p><p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">输入文件的第一行是两个数，<span lang="EN-US">k</span>（<span lang="EN-US">1&lt;=k&lt;=100</span>）和<span lang="EN-US">t(1&lt;=t&lt;=100)</span>。其中<span lang="EN-US">k</span>表示需要选择获利第<span lang="EN-US">k</span>大的方案；<span lang="EN-US">t</span>表示顾客的身份共划分为<span lang="EN-US">t</span>类。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">第二行是一个数<span lang="EN-US">y</span>，表示下一年的年份。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">第三行是一个数<span lang="EN-US">r(0&lt;=r&lt;=20000)</span>，表示共有<span lang="EN-US">r</span>个预订要求。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">以下<span lang="EN-US">r</span>行每行是一个预订要求，格式为：</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span lang="EN-US" style="font-family: 宋体; mso-bidi-font-size: 10.0pt">m1/d1 TO m2/d2 id;</span></span><span lang="EN-US" style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">其中<span lang="EN-US">m1/d1</span>和<span lang="EN-US">m2/d2</span>分别表示到达和离去日期。<span lang="EN-US">id</span>是一个整数（<span lang="EN-US">1&lt;=id&lt;=t</span>），用来标识预订顾客的身份。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt; mso-hansi-font-family: 'Times New Roman'; mso-ascii-font-family: 'Times New Roman'">最后</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font face="Times New Roman">t</font></span><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt; mso-hansi-font-family: 'Times New Roman'; mso-ascii-font-family: 'Times New Roman'">行每行为一个整数</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font face="Times New Roman">P<sub>i</sub>(1&lt;=i&lt;=t</font></span><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt; mso-hansi-font-family: 'Times New Roman'; mso-ascii-font-family: 'Times New Roman'">，</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font face="Times New Roman">1&lt;=P<sub>i</sub>&lt;=32767)</font></span><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt; mso-hansi-font-family: 'Times New Roman'; mso-ascii-font-family: 'Times New Roman'">，表示蜜月房对于身份代号为</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font face="Times New Roman">i</font></span><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt; mso-hansi-font-family: 'Times New Roman'; mso-ascii-font-family: 'Times New Roman'">的顾客的日收费标准。</span></span><span lang="EN-US" style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">例：某对顾客于</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><st1:chsdate year="2011" month="6" day="1" islunardate="False" isrocdate="False" w:st="on"><span style="font-size: medium"><span lang="EN-US">6</span>月<span lang="EN-US">1</span>日</span></st1:chsdate><span style="font-size: medium">到达，</span><st1:chsdate year="2011" month="6" day="3" islunardate="False" isrocdate="False" w:st="on"><span style="font-size: medium"><span lang="EN-US">6</span>月<span lang="EN-US">3</span>日</span></st1:chsdate><span style="font-size: medium">离去，对他们的日收费标准为<span lang="EN-US">m</span>元<span lang="EN-US">/</span>天，则他们共住店两天，需付钱</span><st1:chmetcnv w:st="on" unitname="m" sourcevalue="2" hasspace="False" negative="False" numbertype="1" tcsc="0"><span style="font-size: medium"><span lang="EN-US">2m</span></span></st1:chmetcnv><span style="font-size: medium">元。</span><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt; text-indent: 24pt"><span style="font-size: medium"><span lang="EN-US" style="font-family: 宋体; mso-bidi-font-size: 10.0pt"><o:p>&nbsp;</o:p></span></span><span lang="EN-US" style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><o:p></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"></p></p><hr/><h3>输出格式</h3><p><p class="MsoNormal" style="margin: 0cm 0cm 0pt"><span style="font-size: medium"><span lang="EN-US" style="font-family: 宋体; mso-bidi-font-size: 10.0pt"><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span></span><span style="font-family: 宋体; mso-bidi-font-size: 10.0pt">输出文件仅包含一个整数<span lang="EN-US">p</span>，表示在获利第<span lang="EN-US">k</span>大的方案下，宾馆的年度总收入额。如果获利第<span lang="EN-US">k</span>大的方案不存在，则输出<span lang="EN-US">-1</span>。</span></span><span style="font-size: 12pt; font-family: 宋体; mso-bidi-font-size: 10.0pt"><span lang="EN-US"><o:p></o:p></span></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 0pt"></p></p><hr/><h3>样例输入</h3><pre>1 1
2000
4
1/1 TO 1/2 1
2/1 TO 2/2 1
3/1 TO 3/2 1
2/28 TO 3/3 1
1
</pre><hr/><h3>样例输出</h3><pre>6</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2540" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2540" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>